Vào ngày 21 tháng 7 năm 2000, Tổng thống Ba Lan Aleksander Kwaśniewski đã trao tặng danh hiệu dân sự cao quý thứ nhì của Ba Lan, Đại Thập tự của Huân chương Polonia Restituta, cho Marian Rejewski và Henryk Zygalski.[1] Vào tháng 7 năm 2005, con gái của Rejewski, Janina Sylwestrzak, đã thay mặt ông lên nhận Huân chương Chiến tranh 1939–1945 từ Tham mưu trưởng Bộ Quốc phòng Anh.[2] Ngày 1 tháng 8 năm 2012, Marian Rejewski cũng được truy tặng Giải thưởng Knowlton bởi Hiệp hội Quân đoàn Tình báo Quân đội Hoa Kỳ.[29] Người con Janina của ông đã thay cha nhận giải thưởng này tại quê nhà của ông, Bydgoszcz, vào ngày 4 tháng 9 năm 2012. Rejewski còn được NATO đề cử Giải thưởng Chỉ huy phản gián của quân Đồng minh.[3]

Vào năm 2009, Bưu điện Ba Lan đã phát hành một bộ bốn chiếc tem kỷ niệm, trong đó có một chiếc in hình Rejewski cùng những người cộng sự, Jerzy Różycki và Henryk Zygalski.[30]

Vào ngày 5 tháng 8 năm 2014, Hội Kỹ sư Điện và Diện tử (IEEE) đã vinh danh Rejewski, Różycki và Zygalski với giải thưởng Milestone danh giá, một giải thưởng chuyên ghi nhận những thành tựu làm thay đổi thế giới.[4][5]

Một tượng đài ba mặt bằng đồng đã được khánh thành vào năm 2007 trước Lâu đài Hoàng gia ở Poznań. Mỗi mặt của tượng đài đều mang tên của một trong ba nhà toán học Ba Lan đã giải được mật mã Enigma.[31]

Rejewski và các cộng sự còn được được tái hiện như những người anh hùng trong bộ phim giật gân Sekret Enigmy (Bí mật Enigma), nói về cách mà người Ba Lan đã giải mã được cỗ máy Enigma của quân đội Đức. Vào khoảng cuối những năm 1980, một phim truyền hình Ba Lan có nội dung tương tự có tựa đề Tajemnice Enigmy ("Những bí mật của Enigma") cũng được công chiếu.[32]

Vào năm 2021, Trung tâm Mật mã Enigma, một tổ chức giáo dục và khoa học có tên gọi nhằm vinh danh những nhà toán học Ba Lan đã phá giải mật mã Enigma, trong đó có Marian Rejewski, đã mở cửa hoạt động tại Poznań.[33]